package algorithm.sort;

import java.util.ArrayList;
import java.util.Arrays;

import org.apache.commons.lang3.ArrayUtils;

/**
 * 桶排序
 * 
 * @author jyzjyz12@163.com
 * @since 2017年3月6日 下午1:37:56
 */
public class BucketSortTest1 {

    public static void main(String[] args) {
        int[] arr1 = { 4, 7, 5, 6, 1, 3, 8 };
        int[] arr2 = { 7, 6, 5, 4, 3, 2, 1 };
        int[] arr3 = { 5, 9, 3, 7, 8, 6, 1, 2, 4 };
        int[] arr4 = { 13, 2, 5, 4, 88, 76, 68, 87, 55, 88, 88, 77, 67, 99, 100, 5, 53, 52, 51, 66 };
        System.out.println(Arrays.toString(sort(arr1)));
        System.out.println(Arrays.toString(sort(arr2)));
        System.out.println(Arrays.toString(sort(arr3)));
        System.out.println(Arrays.toString(sort(arr4)));
    }

    public static int[] sort(int[] arr) {
        int[] result = new int[arr.length];
        Node[] buckets = new Node[11];// 11个桶,数组里的数字是0-100之间的,到底选取几个桶,取决于具体排序的数字范围
        for (int i = 0; i < arr.length; i++) {
            int index = arr[i] / 11;
            if (buckets[index] == null) {
                buckets[index] = new Node(arr[i]);
            } else {
                Node newNode = new Node(arr[i]);
                newNode.next = buckets[index];
                buckets[index] = newNode;
            }

        }

        int position = 0;// 将各个bucket里的数据复制到result中,所以记录下当前bucket要从result中的哪个位置开始复制
        for (Node bucket : buckets) {
            if (bucket == null) { // 空的桶
                continue;
            }
            Integer[] one = Node.getAllValue(bucket);// 这个桶中的所有数值
            System.arraycopy(QuickSortTest1.getSortedArr(ArrayUtils.toPrimitive(one)), 0, result, position, one.length);// 把每个bucket中的数值复制到result中,每个bucket里的数值用之前写的快速排序去排序
            position += one.length;
        }
        return result;
    }

    private static class Node {
        public static Integer[] getAllValue(Node n) {
            ArrayList<Integer> result = new ArrayList<Integer>();// 这里导致了int[]和integer[]之间的转化,但是也没啥办法,因为不知道这个bucket里有多少个数值,或者之前不要用Node[]了,直接用ArrayList<ArrayList<Integer>>
            while (n != null) {
                result.add(n.value);
                n = n.next;
            }
            return result.toArray(new Integer[0]);
        }

        public int value;
        public Node next;

        public Node(int value) {
            this.value = value;
        }
    }
}
